package 二叉树;

import 我的JDK基础数据结构.HashMap.HashMap;

import java.util.Map;

public class No106从中序与后序遍历序列构造二叉树 {

    /**
     * 根据一棵树的中序遍历与后序遍历构造二叉树。
     * 注意:
     * 你可以假设树中没有重复的元素。
     *
     * 例如，给出
     * 中序遍历 inorder = [9,3,15,20,7]
     * 后序遍历 postorder = [9,15,7,20,3]
     * 返回如下的二叉树：
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     */

    private int[] postorder;
    private Map<Integer,Integer> map;

    //只知道前序和后序遍历序列，是无法知道哪个结点是左子树还算右子树。
    //中序遍历,永远的神
    public TreeNode buildTree(int[] inorder, int[] postorder) {

        this.postorder=postorder;
        map=new HashMap<>();

        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }

        return dg(0,inorder.length-1,0,postorder.length-1);
    }

    private TreeNode dg(int inLeft,int inRight,int poLeft,int poRight){

        if(inLeft>inRight||poLeft>poRight){
            return null;
        }

        TreeNode root=new TreeNode(postorder[poRight]);

        int inMid=map.get(postorder[poRight]);

        root.left=dg(inLeft,inMid-1,poLeft,poLeft+(inMid-inLeft)-1);

        root.right=dg(inMid+1,inRight,poLeft+(inMid-inLeft),poRight-1);

        return root;
    }

}
